package day05;

public class 回文链表 {
    /*class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null) {
                return true;
            }
            // 创建一个新的链表，用于存储逆序后的链表
            ListNode head2 = new ListNode(0);
            ListNode cur = head;

            // 逆序链表，不修改原始链表
            while (cur != null) {
                // 创建一个新节点，值为当前节点的值
                ListNode newNode = new ListNode(cur.val);
                // 将新节点插入到新链表的头部
                newNode.next = head2;
                head2 = newNode;
                // 移动到下一个节点
                cur = cur.next;
            }

            // 比较原始链表和逆序后的链表
            ListNode cur1 = head;
            ListNode cur2 = head2;
            while (cur1 != null && cur2 != null) {
                if (cur1.val != cur2.val) {
                    return false;
                }
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return true;
        }
    }*/

    class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null) {
                return true;
            }
            // 使用快慢双指针(第一个中间结点)
            ListNode slow = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }

            ListNode cur = slow.next;
            slow.next = null;
            ListNode head2 = new ListNode(0);
            while (cur != null) {
                ListNode curNext = cur.next;
                cur.next = head2.next;
                head2.next = cur;
                cur = curNext;
            }

            ListNode cur1 = head, cur2 = head2.next;
            while (cur1 != null && cur2 != null) {
                if (cur1.val != cur2.val) {
                    return false;
                }
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return true;
        }
    }
}
